\chapter{Simulationsumgebung}
\label{cha:simulationsumgebung}

Das Kapitel der Simulationsumgebung befasst sich mit den Eingabemöglichkeiten zur Anpassung der Simulationsparameter, sowie der konkreten Umsetzung der simulierten Welt, mit der Logik für die Notausgänge, der Personen, der Gefahrensituationen und den jeweiligen Kommunikationsmodellen.

Die Ausgangsbasis für die verwendeten Modelle und Protokolle stammen aus den erstellten Übungen zur Vorlesung Gensensornetze, sie wurden jedoch auf die Anforderungen der Hausarbeit adaptiert.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Benutzerschnittstelle}
\label{sec:benutzerschnittstelle}

In diesem Abschnitt werden die Interaktions- und Konfigurationsmöglichkeiten mit der Simulationsumgebung erläutert. Abbildung \ref{fig:gui} stellt einen Ausschnitt des grafischen Interfaces von NetLogo da, anhand dessen die Erklärungen in den folgenden Abschnitten besser einzuordnen sind. 

\begin{figure}[!ht]
\centering
\includegraphics[height=0.85\textwidth]{simulationsumgebung/gui_3}
\caption{Grafische Oberfläche}
\label{fig:gui}
\end{figure}

\subsection{Benutzerevents}
\label{sec:gui_userevents}

Zum Auslösen von Benutzerevents werden Buttons verwendet. Zu diesen zählen \verb|setup|, \verb|reset| und \verb|go|, die hier kurz beschrieben werden.

\subsubsection*{setup-Button}

Die Betätigung des \verb|setup|-Buttons ruft eine Folge von Setup und Initialisierungsschritten auf. Zu Beginn wird die Simulationswelt erstellt. Dazu wird der Parameter \verb|inputFile| (siehe Abschnitt \ref{sec:gui_general}) zum Einbinden einer Bild-Datei und das Mapping der Pixel-Farbwerte auf die passend skalierte NetLogo-Welt gemappt. Das Ergebnis ist der gewählte Grundriss, bei dem jedes Patch einen Farbwert erhalten hat.

Dieser Farbwert ist essentiell für den nachfolgenden Schritt in der \verb|setup-patches|-Funktion. Diese legt den Initialzustand jedes Patches fest (siehe Abschnitt \ref{sec:patches}). Generell wird auf Grund des Grundrisses zwischen leerem Raum (weiß) und einer Wand unterschieden (schwarz). 

Wände spielen auch bei der Initialisierung und Platzierung der Notausgänge eine wichtige Rolle, die mit der \verb|setup-exits|-Funktion realisiert sind. Entsprechend der Aufgabenstellung werden Notausgänge auf einem abstrakten Grundriss, ohne Wände, zufällig in der Welt platziert. Für alle anderen Grundrisse mit Wänden wird auf statische vordefinierte Positionen für Notausgänge gesetzt.\par
Bei der Initialisierung wird zudem die lokale Konstante der maximalen Signalreichweite für den Orientierungsalgorithmus \emph{cellular automaton} mit dem Parameter \verb|exit-signal-strength| aus Abschnitt \ref{sec:gui_exit} gesetzt und alle Notausgänge in den Zustand \emph{INIT} versetzt (vgl. Abschnitt \ref{sec:notausgaenge}).\par
Im Anschluss wird der \emph{cellular automaton}-Algorithmus (siehe Abschnitt \ref{sec:cellular_automaton}) ausgeführt, um die Patches mit Signalqualitätsinformationen auszustatten, damit die Personen den optimalen Fluchtweg bei einer Gefahrensituation nutzen.

Nachdem die Simulationswelt mit den statischen Elementen vorbereitet wurde, werden die Personen initialisiert und platziert. Dies geschieht mit der Methode \verb|setup-persons|. Hier wird eine definierte Anzahl von Personen erstellt (siehe Abschnitt \ref{sec:gui_person}, die auf einem abstrakten Grundriss zufällig und auf allen anderen zufällig mit einer Wand-Detektion platziert werden. Die Personen befinden sich nun im Zustand \emph{INIT} (vgl. Abschnitt \ref{sec:bewegungsmodell}).\par
Nach der Platzierung wird einmalig ein Kommunikationsgraph zwischen den Personen und den Notausgängen erstellt, damit der Nutzer ggf. den Graph-Typen oder die Kantenlänge anpassen kann (siehe Abschnitt \ref{sec:gui_person}).
 
Als letzter Schritt folgt die Initialisierung und Platzierung der Gefahrenevents  mittels \verb|setup-events|. Die analog zu den Personen auf dem abstrakten Grundriss zufällig und bei allen anderen Grundrissen mit Wand-Detektion platziert werden. Danach befinden sich alle Gefahrenevents im Zustand \emph{INIT} (vgl. Abschnitt \ref{sec:gefahrensituationen}).
 
\subsubsection*{reset-Button}

Mit dem \verb|reset|-Button werden alle definierten Parameter des letzten Setups wiederhergestellt und die Personen auf ihre ursprüngliche Position zurückgesetzt.
Ein fluten des Grundrisses ist nicht erneut erforderlich und beschleunigt das Durchführen von Messreihen.
Zudem bietet es die Möglichkeit den Kommunikationsgraphen der Personen auszublenden, dies ist unter anderem nützlich bei der Darstellung der initial approximierten Positionen der Personen.

\subsubsection*{go-Button}

Schließlich kann die Simulation mit dem \verb|go|-Button gestartet und pausiert werden, da hier die \emph{forever}-Option aktiv ist. Ist diese deaktiviert, wird pro Betätigung des \verb|go|-Buttons nur ein \emph{Tick} durchgeführt.

\subsection{Generelle Parameter}
\label{sec:gui_general}

Der Parameter \verb|input-file| erlaubt die Definition des Grundrisses der Simulationsumgebung. Während des Setups wird der Parameter zur Pfadauflösung für eine Bild-Datei verwendet. Diese wird mit dem Befehl \verb|import-pcolors inputFile| auf die Simulationswelt gemappt.

\begin{quote}
\verb|input-file| $\in \{Abstract.png, Abstract\_static.png, Simple.png,$ \\\hspace*{2.6cm}$Raumplan.png\}$
\end{quote}

Der nächste generelle Parameter ist \verb|orientation-algorithm|. Dieser dient der Auswahl eines Algorithmus zur Orientierung und Lokalisierung der Personen. Detaillierte Informationen sind im Kapitel \ref{cha:algorithmik} aufgeführt.

\begin{quote}
\verb|orientation-algorithm| $\in \{Cellular$ $automaton,$\\\hspace*{4.9cm}$Multilateration$ $localization\}$
\end{quote}

Mit dem \verb|graph-type|-Parameter hat der Nutzer die Wahl zwischen den Graphtypen, die in der Vorlesung vorgestellt wurden. Sofern \emph{UDG} gewählt ist, wird der \verb|person-detection-radius|-Parameter des folgenden Abschnitts für den Disk-Radius verwendet.

\begin{quote}
\verb|graph-type| $\in \{Complete$ $Graph, UDG, RNG, GG\}$
\end{quote}

\subsection{Personen--Parameter}
\label{sec:gui_person}

\verb|person-count| definiert die Anzahl der Personen in der Simulationsumgebung.

\begin{quote}
\verb|person-count| $\in [1, 300]$
\end{quote}

Mit dem \verb|walk-probability|-Parameter wird die Wahrscheinlichkeit definiert, mit der Personen bei einem Tick einen Schritt machen. Bei $0 \%$ werden die Personen statisch an der gegenwärtigen Position fixiert. Es ist also möglich diesen Parameter während der Laufzeit zu verändern.  

\begin{quote}
\verb|walk-probability| $\in [0, 100]$
\end{quote}

Der \verb|walk-strategy|-Parameter erlaubt die Auswahl der \emph{random walk}-Strategie (siehe Abschnitt \ref{sec:bewegungsmodell}).

\begin{quote}
\verb|walk-strategy| $\in \{Complete$ $random, Straight$ $with$ $collision$ $detection,$\\\hspace*{3.2cm}$Straight$ $with$ $probability\}$
\end{quote}

Analog zur \verb|walk-probability| kann der Nutzer den \verb|random-walk-probability|-Parameter zur Laufzeit anpassen und somit die Wahrscheinlichkeit der \emph{random walk} Richtungsänderung bestimmen. Bei $100 \%$ wird jede Person nach jedem Tick eine Richtungsänderung vornehmen.

\begin{quote}
\verb|random-walk-probability| $\in [0, 100]$
\end{quote}

Der \verb|person-detection-radius|-Parameter ist einer der entscheidendsten bei der Simulation. Hiermit wird der Radius definiert in dem eine Person eine Gefahrensituation wahrnehmen kann, sowie die Kommunikationsreichweite bei dem UDG-Graphen bestimmt.

\begin{quote}
\verb|person-detection-radius| $\in [0, 300]$
\end{quote}



\subsection{Event--Parameter}
\label{sec:gui_event}

Mit dem Parameter \verb|event-count| wird die Anzahl der zu platzierenden Gefahrenevents festgelegt. Bei \verb|event-count| $ = 0$ wird es zu keiner Gefahrensituation kommen, sodass der \emph{random walk} getestet werden kann.

\begin{quote}
\verb|event-count| $\in [0, 20]$
\end{quote}

In der Aufgabenstellung wird ein zufälliges Auslösen von Gefahrensituationen gefordert, die beiden Parameter \verb|min-countdown| und \verb|max-countdown| bewerkstelligen dies. Jedes einzelne Gefahrenevent erhält zufällig einen initialen Countdown im Intervall $[$\verb|min-countdown|, \verb|max-countdown|$]$. Die obere bzw. untere Intervallgrenze der Parameter wird durch den jeweils anderen Parameter eingeschränkt.  

\begin{quote}
\verb|min-countdown| $\in [1, $\textit{max-countdown}$]$
\end{quote}

\begin{quote}
\verb|max-countdown| $\in [$\textit{min-countdown}$, 100]$
\end{quote}

Der Parameter \verb|gas-expansion-probability| legt für alle Gefahrenevents die Ausbreitungswahrscheinlichkeit und somit die Ausbreitungsgeschwindigkeit fest. Bei $0 \%$ wird nur genau ein Patch unter dem jeweiligen Gefahrenevent zu einer Bedrohung für die Personen. Personen können die Gefahrensituationen somit wahrnehmen, die Wahrscheinlichkeit das Personen sterben ist jedoch sehr gering. 

\begin{quote}
\verb|gas-expansion-probability| $\in [0, 100]$
\end{quote}


\subsection{Notausgang--Parameter}
\label{sec:gui_exit}

Der Parameter zur Einstellung der verfügbaren Notausgänge in der simulierten Welt, 
\verb|number-of-exits| ist sehr bedeutsam bei der Lokalisierungsgenauigkeit und dem Fluchtverhalten der Personen.

\begin{quote}
\verb|number-of-exits| $\in [1, 9]$
\end{quote}

Zur dezentralen Orientierung der Personen und Schaffung eines optimalen Fluchtweges, wird auf zelluläre Automaten zurückgegriffen und die Patches mit Informationen zur Signalstärke jedes Notausganges versehen.\par
Der Parameter \verb|exit-signal-strength| bildet die maximale Signalstärke bzw. Reichweite der Notausgänge ab. Es ist möglich, dass nicht jedes Patch mit allen Signalinformationen versehen ist, da die Reichweite eines Notausganges zu gering war.

\begin{quote}
\verb|exit-signal-strength| $\in [0, 400]$
\end{quote}

Die Aufgabenstellung fordert eine Limitierung Fluchtkapazitäten von Notausgängen. D.h. Notausgänge können maximal \verb|exit-limit| Personen pro Tick evakuieren, sonst werden sie blockiert.

\begin{quote}
\verb|exit-limit| $\in [1, 300]$
\end{quote}

\subsection{Multilateration localization--Parameter}
\label{sec:gui_localization}

Der Parameter \verb|locate-iterations| bestimmt, wie viele Iterationen der Algorithmus durchführen soll. Je höher diese Zahl ist, desto genauer wird die Lokalisierung mit dem Algorithmus. Jedoch erfordert dies mehr Rechenzeit. Dieser Parameter ist für die Evaluierung mit dem  \emph{Multilateration Algorithmus} nötig, da man so bestimmen kann, ab wie vielen Iterationen bereits vernünftige Ergebnisse herauskommen und ab wann es sich nicht mehr lohnt in Relation mit der Rechenzeit.

\begin{quote}
\verb|locate-iterations| $\in [0, 100]$
\end{quote}

Da der Algorithmus den \emph{Hop Count} (vorgestellt in \ref{sec:gradient_localization}) benutzt um die Distanz zu den Bezugspunkten (in diesem Fall die Notausgänge) zu bestimmen, braucht der Algorithmus auch eine Abschätzung, wie viele Patches ein hop zu einer Person repräsentiert. Das heißt, eine Person mit einem hop count n zum Notausgang x hat eine geschätzte Distanz zu x von n * approx-dist. Für die Evaluation müssen verschiedene Werte ausprobiert werden, abhängig davon, wie der Kommunikationsgraph aufgebaut wird und wie viele Personen in der Simulation leben.

\begin{quote}
\verb|approx-dist| $\in [0, 200]$
\end{quote}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Personen}
\label{sec:personen}

Personen sind Agenten, die mit NetLogo als \emph{breed} modelliert werden. Mit einem \emph{breed} kann das Konzept der Kapselung aus der Objektorientierung realisiert werden. Im Kontext einer Person können lokale Variablen deklariert werden, die von den abstrakten Variablen des \emph{breeds} vererbt werden. 

Mit diesem Konzept wird ein Lebenszyklus mit verschiedenen Zuständen und Zustandsübergängen für die Personen modelliert. 

% Lifecycle
\subsection{Lebenszyklus}

Der Lebenszyklus bestimmt das Verhalten der Personen. Die Zustände und die Zustandsübergänge werden in Abbildung \ref{fig:person} mittels eines Zustandsdiagramms beschrieben. 

Nach der Platzierung in der simulierten Welt befinden sich alle Personen im Zustand \verb|INIT|. In diesem Zustand wird ein \emph{random walk} ausgeführt. Die verschiedenen Typen werden im Abschnitt \ref{sec:bewegungsmodell} näher erläutert.

Nimmt eine Person in ihrem Sichtradius \verb|person-detection-radius| ein Gefahrenevent war, geht die Person in den Zustand \verb|EVENT_DETECTED| über. Hier versucht die Person andere Personen in der Umgebung zu warnen. Näheres ist dem Kommunikationsmodell im Abschnitt \ref{sec:kommunikationsmodell} zu entnehmen.

Nach dem Benachrichtigungsversuch wechselt die Person in den Zustand \verb|FLEEING|, bei dem die Person vor der Gefahrensituation flüchtet und versucht einen Notausgang zu erreichen. Zur Flucht wird ein anderes Bewegungsmodell verwendet, welches im Abschnitt \ref{sec:bewegungsmodell} beschrieben wird. Während der Flucht kann die Person weitere Gefahrensituation detektieren.

Erreicht die Person einen nicht blockierten Notausgang, ist sie gerettet und im Zustand \verb|RESCUED|. Die Person wird aus der Simulationsumgebung entfernt.

Bei einer Berührung mit dem Giftgas stirbt eine Person jedoch immer. Sie ist dann im Zustand \verb|DEAD|. Eine Interaktion mit ihr ist nicht mehr möglich. 

% INIT
% INIT, DEAD
% INIT, RESCUED
% INIT, EVENT_DETECTED, DEAD
% INIT, EVENT_DETECTED, FLEEING, RESCUED
% INIT, EVENT_DETECTED, FLEEING, DEAD

\begin{figure}
\centering
\includegraphics[height=0.6\textwidth]{simulationsumgebung/person.eps}
\caption{Zustandsdiagramm der Personen}
\label{fig:person}
\end{figure}

\subsection{Bewegungsmodell}
\label{sec:bewegungsmodell}
%Bewegungsmodell: Die Agenten sollen sich nach einem „Random Walk“ Modell bewegen. Agenten können Gefahren in ihrer Umgebung wahrnehmen und die Information an ihre nächs-ten Nachbarn weitergeben. Sobald ein Agent Informationen über eine Gefahrensituation hat, soll er sich auf dem kürzesten Weg zum nächsten Notausgang bewegen.  Hat ein Agent die Umgebung eines Notausgangs erreicht, soll er aus der Simulation genommen werden.

Für die Personen existieren zwei unterschiedliche Bewegungsmodelle, zum einen für Personen im \verb|INIT| Zustand und zum anderen für Personen im \verb|FLEEING| Zustand. Beide Modelle werden folgend erklärt.

\subsubsection{Initiales Bewegungsmodell}
\label{sec:init_walk}

%\verb|walk-strategy| $\in \{Complete$ $random, Straight$ $with$ $collision$ $detection,$\\\hspace*{3.2cm}$Straight$ $with$ $probability\}$

Für das initiale Bewegungsmodell kann der Nutzer zwischen drei Arten eines \emph{random walks} wählen. Der rudimentäre \emph{random walk} wird in Algorithmus \ref{alg:random_walk} beschrieben. Dieser dient als Grundlage für die weiteren Arten.


\floatname{algorithm}{Algorithmus} 
\begin{algorithm}
\caption{random-walk}
\label{alg:random_walk}
\begin{algorithmic} 
\STATE nb $\leftarrow$ one-of neighbors
\WHILE{\textit{[patch-state] of nb = WALL}}
\STATE nb $\leftarrow$ one-of neighbors 
\ENDWHILE
\STATE face nb
\STATE forward 1
\end{algorithmic}
\end{algorithm}

Algorithmus \ref{alg:random_walk} beschreibt die Wahl eines benachbarten Patches, welche als Wahl einer von acht neuen Richtungen interpretiert werden kann. Bei dem Algorithmus wird lediglich auf eine Wand-Kollision geprüft und solange eine Wand in der beabsichtigten Richtung steht, wird eine neue Richtung gesucht.

Eine weitere Strategie für den \emph{random walk} ist \verb|straight with collision detection|. Dabei speichert eine Person lokal die letzte Orientierung, das sogenannte \verb|heading|, und bewegt sich in diese Richtung bis zu einer Wand-Detektion. An dieser Stelle wird Algorithmus \ref{alg:random_walk} ausgeführt und die neue Orientierung gespeichert.

Bei der letzten Strategie \verb|straight with probability| wird auch die letzte Orientierung lokal gespeichert, hier bestimmt jedoch der \verb|random-walk-probability|-Parameter die Wahrscheinlichkeit der Ausführung von Algorithmus \ref{alg:random_walk}. Eine Wand-Detektion wird zusätzlich durchgeführt.

\subsubsection{Bewegungsmodell bei der Flucht}
\label{sec:move_to_exit}

Nachdem eine Person ein Gefahrenevent wahrgenommen hat, flieht sie zu dem nächsten verfügbaren Notausgang. Der optimale Fluchtweg wird über Informationen der Signal-Stärke von Notausgängen von den Personen lokal ermittelt. Abbildung \ref{fig:fleeing} zeigt exemplarisch den Fluchtweg einer Person. Für die Algorithmik zur Wertevergabe auf den Patches sei auf Kapitel \ref{cha:algorithmik} verwiesen. 

\begin{figure}[!ht]
\centering
\includegraphics[height=0.65\textwidth]{simulationsumgebung/fleeing}
\caption{Fluchtwegermittlung}
\label{fig:fleeing}
\end{figure}

Der Algorithmus für die Fluchtwegbestimmung wird auf Grund der hohen Komplexität an dieser Stelle nicht komplett vorgestellt. Da zum Beispiel die Verfügbarkeit von Notausgängen oder Ausnahmebehandlungen berücksichtigt werden müssen. Das Prinzip verdeutlicht Algorithmus \ref{alg:fleeing}. Bei dem die Person in der lokalen Umgebung nach dem Patch mit der geringsten Zahl bzw. der geringsten Dämpfung des Signals eines Notausgangs sucht. 

\floatname{algorithm}{Algorithmus} 
\begin{algorithm}
\caption{person-move-to-exit}
\label{alg:fleeing}
\begin{algorithmic} 
\STATE nb $\leftarrow$ -1
\STATE min-noise $\leftarrow$ $\infty$
\STATE ask neighbors [\hfill\emph{; iterate all 8 neighbors}
\IF{$min$-$noise > signal$-$noise$}
\STATE min-noise $\leftarrow$ signal-noise\hfill\emph{; define best signal and direction}
\STATE nb $\leftarrow$ self
\ENDIF 
\STATE ]
\STATE face nb
\STATE forward 1
\end{algorithmic}
\end{algorithm}




Die Information über die Verfügbarkeit eines Notausganges wird von diesem durch das Kommunikationsnetzwerk der Personen gebroadcastet. Eine Beschreibung dazu ist dem Abschnitt \ref{sec:notausgaenge_kommunikation} Kommunikationsmodell der Notausgänge zu entnehmen.

\subsection{Kommunikationsmodell}
\label{sec:kommunikationsmodell}
%Kommunikationsmodell: Als Kommunikationsmodell können beliebige Modelle der Vorlesung implementiert werden. Dabei sollte insbesondere auf die dynamische Netzwerktopologie geach-tet werden. 

Für die Warnung anderer Personen wird das Kommunikationsmodell \emph{Basic Flooding} aus der Vorlesung implementiert. Die identifizierende Meldung lautet hier \verb|event-detected| und die beiden Zustände für das \emph{Basic Flooding} werden mit \verb|EVENT_DETECTED| und \verb|FLEEING| ausgedrückt. 

Algorithmus \ref{alg:event_detected} zeigt, zur besseren Einordnung, die Einbettung des Kommunkationsprotokolls in den Lebenszyklus der Person. Es sei darauf hingewiesen, dass auf eine spontane Zustandsänderung einer Person, wie es in dem \emph{Basic Flooding}-Protokoll angegeben ist, verzichtet wird. Die Detektion einer Gefahrensituation präzisiert diesen Zustandsübergang in diesem Fall präziser.

%\floatname{algorithm}{Protokoll} 
\begin{algorithm}
\caption{Warnung vor Gefahrensituationen}
\label{alg:event_detected}
\begin{algorithmic} 
\STATE \textit{State Trans. Sys.:} $\langle\{$INIT, EVENT{\_}DETECTED, FLEEING, RESCUED$\}, \{$INIT, DEAD$\}, \{$INIT, EVENT{\_}DETECTED, DEAD$\}, \{$INIT, EVENT{\_}DETECTED, FLEEING, DEAD$\}, \{$FLEEING, EVENT{\_}DETECTED$\}\rangle$
\STATE \textit{Initialization:} All notes in state INIT
\STATE \textit{Restrictions:} Reliable communication; connected, bidirected communication graph $G = (V,E)$, neighborhoodfunction nbr: $V \rightarrow 2^{V}$
\STATE \textit{Local data:}

\STATE $ $
\STATE \textbf{INIT}
\STATE Receiving(\textit{event{\_}detected})
\WHILE{\textit{not event{\_}detected}}
\STATE random-walk
\STATE create-graph($G$)\hfill\emph{; generate complete new graph}
\ENDWHILE
\STATE become EVENT{\_}DETECTED
\IF{touching-gas}
\STATE become DEAD
\ENDIF

\STATE $ $
\STATE \textbf{EVENT{\_}DETECTED}
\STATE broadcast(\textit{event{\_}detected})\hfill\emph{; broadcast event detection to linked neighbors}
\STATE become FLEEING
\IF{touching-gas}
\STATE become DEAD
\ENDIF

\STATE $ $
\STATE \textbf{FLEEING}
\IF{msg = event-detected}
\STATE broadcast(\textit{event{\_}detected})\hfill\emph{; forwarding event detection msg to linked neighbors}
\ENDIF
\WHILE{\textit{not person-reach-exit}}
\STATE person-move-to-exit\hfill\emph{; using orientation-algorithm}
\STATE create-graph($G$)\hfill\emph{; generate complete new graph}
\IF{event{\_}detected}
\STATE become EVENT{\_}DETECTED
\ENDIF
\IF{touching-gas}
\STATE become DEAD
\ENDIF
\ENDWHILE
\STATE become RESCUED

\STATE $ $
\STATE \textbf{RESCUED}
\STATE create-graph($G$)\hfill\emph{; generate complete new graph without note}

\STATE $ $
\STATE \textbf{DEAD}
\STATE create-graph($G$)\hfill\emph{; generate complete new graph without note}

\end{algorithmic}
\end{algorithm}

Das Fluten mit Meldungen ist jedoch ohne eine sinnvolle Netzwerktopologie nicht möglich. Mit dem Parameter \verb|graph-type| hat der Nutzer die Möglichkeit den Graph-Typen des Kommunikationsnetzwerks anzupassen. 

Allerdings wird in den meisten Fällen keine statische Knoten-Positionierung vorliegen\footnote{Eine statische Knoten-Positionierung wird mit $walk$-$probability = 0$ erzielt.}. Es wird daher nach jedem Tick der gesamte Kommunikationsgraph neu aufgebaut. Auf eine Ausnahmebehandlung für Personen ohne Positionsänderung wird verzichtet.

Zur visuellen Unterstützung erhalten Personen im Zustand \verb|EVENT_DETECTED| das Label \glqq !{\grqq}. Der initiale Broadcast zur Warnung anderer Personen wird mit orange gefärbten Kanten und der Zustand \verb|FLEEING| mit dem Label \glqq *{\grqq} ausgedrückt.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Notausgänge}
\label{sec:notausgaenge}
%Notausgänge: Notausgänge sollen als statische Sensorknoten modelliert werden, die ihre Po-sition sowie Information zu ihrer Passierbarkeit im Netz verteilen. Die Positionen dieser sog. anchor nodes sollen zur Positionierung der mobilen Sensorknoten verwendet werden (Algorithmik). Während einer Simulation sollte der Ausfall einzelner Notausgänge simuliert werden.

Notausgänge sind statische Agenten, für die eine eigene \emph{breed} analog zu den Personen angelegt wurde. Die Notausgänge verfügen über einen Lebenszyklus und ein Kommunikationsmodell zur Übermittlung ihrer Zustandsinformationen an nahe Personen. 

%Lifecycle
\subsection{Lebenszyklus}

% INIT, NEGOTIABLE
% INIT, NEGOTIABLE, BLOCKED

Der Lebenszyklus eines Notausgangs ist in drei Zustände unterteilt. Im Zustand \verb|INIT| befinden sich alle Notausgänge nach der Platzierung auf der Welt. Während des Zustandsübergangs zu \verb|NEGOTIABLE| wird die Logik für den gewählten Orientierungsalgorithmus ausgeführt. In der Regel wird die Welt mit Signalinformationen ausgehend von jedem Notausgang geflutet. Der Algorithmus wird in Kapitel \ref{cha:algorithmik} vorgestellt. Die Ausführung dauert entsprechend der (Patch-)Auflösung lange.

Ist ein Notausgang im Zustand \verb|NEGOTIABLE|, bestehen zwei Möglichkeiten in den Zustand \verb|BLOCKED| zu gelangen. Temporär blockiert ist ein Notausgang, wenn zu viele Personen gleichzeitig versuchen das Gebäude zu verlassen. Der Parameter \verb|exit-limit| definiert die Obergrenze. Nach einem Tick wird der Notausgang wieder zurückgesetzt. Erreicht das Giftgas bzw. die Gefahrensituation einen Notausgang, so wird dieser permanent in den Zustand \verb|BLOCKED| über.

\begin{figure}[!ht]
\centering
\includegraphics[height=0.6\textwidth]{simulationsumgebung/exit.eps}
\caption{Zustandsdiagramm der Notausgänge}
\label{fig:exit}
\end{figure}

%\begin{algorithm}
%\caption{Patch-Flooding (Zellulärer Automat)}
%\begin{algorithmic} 
%\STATE \textit{State Trans. Sys.:} $\langle\{$NONE$\},\{$NONE, SPREADING, IDLE, DONE$\}\rangle$
%\STATE \textit{Initialization:} All patches in state NONE
%\STATE \textit{Restrictions:} orientation-algorithm = $"$Cellular automaton$"$
%\STATE \textit{Global data:} exit-signal-strength $\in \mathbb{N}_{\geq0}$
%\STATE \textit{Local data:} 
%\STATE Set \textit{exits} of exits in range
%\STATE Set \textit{signal-noises} of exit signals
%
%\STATE $ $
%\STATE \textbf{NONE}
%\STATE \textit{Spontaneously}
%\STATE exits $\leftarrow$ myself\hfill\emph{;exit on this patch}
%\STATE signal-noises $\leftarrow$ 0
%\STATE become SPREADING
%
%
%\STATE $ $
%\STATE \textbf{SPREADING}
%\STATE parent-exit $\leftarrow$ exit
%\STATE signal-noise-here $\leftarrow$ signal-noise + 1
%\FOR{? one-of neighbors}
%\IF{[patch-state] of ? = NONE}
%\STATE exits $\leftarrow$ parent-exit
%\STATE signal-noises $\leftarrow$ signal-noise-here
%\ENDIF
%\ENDFOR
%\STATE become IDLE
%
%
%\STATE $ $
%\STATE \textbf{IDLE}
%
%\STATE become DONE
%
%\STATE $ $
%\STATE \textbf{DONE}
%
%\end{algorithmic}
%\end{algorithm}

\subsection{Kommunikationsmodell}
\label{sec:notausgaenge_kommunikation}

Die Notausgänge befinden sich im gleichen Kommunikationsnetzwerk, wie die Personen. Eine Unterscheidung zu anderen Netzwerken bzw. Links wird über Typ-Definitionen und visuell über den Shape durchgeführt.

\floatname{algorithm}{Algorithmus} 
\begin{algorithm}
\caption{Passierbarkeitsmeldungen der Notausgänge}
\label{alg:exit_status}
\begin{algorithmic} 
\STATE \textit{State Trans. Sys.:} $\langle\{$INIT, NEGOTIABLE, BLOCKED$\}, \{$NEGOTIABLE, BLOCKED$\}, \{$BLOCKED, NEGOTIABLE$\}\rangle$
\STATE \textit{Initialization:} All notes in state INIT
\STATE \textit{Restrictions:} Reliable communication; connected, bidirected communication graph $G = (V,E)$, neighborhoodfunction nbr: $V \rightarrow 2^{V}$
\STATE \textit{Local data: current-persons, exit-limit}

\STATE $ $
\STATE \textbf{INIT}
\STATE ...\hfill\emph{; init-orientation-algorithm}
\STATE become NEGOTIABLE

\STATE $ $
\STATE \textbf{NEGOTIABLE}
\STATE negotiable $\leftarrow$ true
\WHILE{$negotiable$}
\STATE broadcast(\textit{exit-negotiable})\hfill\emph{; continious broadcast}
\IF{$current$-$persons > exit$-$limit$}
\STATE negotiable $\leftarrow$ false
\ENDIF
\IF{$gas$-$reached$-$exit$}
\STATE negotiable $\leftarrow$ false
\ENDIF
\ENDWHILE
\STATE become BLOCKED


\STATE $ $
\STATE \textbf{BLOCKED}
\STATE negotiable $\leftarrow$ false
\WHILE{$not negotiable$}
\STATE broadcast(\textit{exit-blocked})\hfill\emph{; continious broadcast}
\IF{$current$-$persons <= exit$-$limit$}
\STATE negotiable $\leftarrow$ true
\ENDIF
\ENDWHILE
\STATE become NEGOTIABLE

\end{algorithmic}
\end{algorithm}

Für die Verbreitung der Passierbarkeit wird das \emph{Basic Flooding} implementiert. Algorithmus \ref{alg:exit_status} zeigt das eingebettete Protokoll innerhalb des Lebenszyklus von Notausgängen. 

Die Notausgänge broadcasten bei Statuswechsel eine positive oder negative Passierbarkeitsmeldung und ihren Identifier im Netzwerk. Personen in Reichweite empfangen die Meldung \verb|exit-blocked| oder \verb|exit-negotiable|, speichern die Information lokal in einem binären Array ab und broadcasten die Meldung an die benachbarten Personen. Bei n = 3 Notausgängen verfügt jede Person über ein n-äres Array mit Nullen oder Einsen. Null steht für blockiert, Eins für passierbar.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Gefahrensituationen}
\label{sec:gefahrensituationen}
%Gefahrenevents: Gefahrenevents erscheinen an zufälligen Orten im Grundriss. Ihr Erscheinen sollte zur vollständigen Evakuierung des Areals führen.

Eine Gefahrensituation liegt vor, wenn mindestens ein Gefahrenevent aktiviert wurde. Die Gefahrenevents werden als \emph{breed} modelliert. 

%Lifecyle
\subsection{Lebenszyklus}

% INIT, COUNTDOWN, GASSING, DONE

Die Zustandsübergänge von Gefahrenevents verlaufen sequentiell. Alle Events beginnen nach der Platzierung im Zustand \verb|INIT| und enden im Zustand \verb|DONE|. Abbildung \ref{fig:event} zeigt ebenfalls die beiden weiteren Zustände \verb|COUNTDOWN| und \verb|GASSING|.

\begin{figure}[!ht]
\centering
\includegraphics[height=0.5\textwidth]{simulationsumgebung/event.eps}
\caption{Zustandsdiagramm der Gefahrenevents}
\label{fig:event}
\end{figure}

Mit dem Start der Simulation gehen alle Events in den Zustand \verb|COUNTDOWN| über, in der lokal vorgehaltene zufällige Countdown pro Tick herunter gezählt wird. Steht der Countdown bei Null, geht das Gefahrenevent in den Zustand \verb|GASSING| über.

In diesem Zustand wird die Freisetzung des Gases initiiert. Die Ausbreitung des Gases ähnelt dem Fluten mit Signal-Informationen auf Kapitel \ref{cha:algorithmik}. 
%Der Algorithmus \ref{alg:event} liefert detailierte Informationen zur Bestimmung des zufälligen Countdowns und der Gasfreisetzung, die im folgenden Abschnitt zu den Patches noch einmal angesprochen wird.

%\begin{algorithm}
%\caption{Gefahrensituation}
%\label{alg:event}
%\begin{algorithmic} 
%\STATE \textit{State Trans. Sys.:} $\langle\{$INIT, COUNTDOWN, GASSING, DONE$\}\rangle$
%\STATE \textit{Initialization:} All notes in state INIT
%\STATE \textit{Restrictions:} All patches in state $\{$NONE, DONE$\}$
%\STATE \textit{Local data:} countdown $\in \mathbb{N}_{\geq0}$ 
%\STATE $ $
%\STATE \textbf{INIT}
%\STATE \textit{Spontaneously}
%
%\STATE countdown $\leftarrow$ minCountdown + (random (maxCountdown - minCountdown))
%\STATE become COUNTDOWN
%
%
%\STATE $ $
%\STATE \textbf{COUNTDOWN}
%\STATE countdown $\leftarrow$ countdown - 1
%\IF{$countdown = 0$}
%\STATE become GASSING
%\ENDIF
%
%\STATE $ $
%\STATE \textbf{GASSING}
%\STATE ask patch-here $[$ patch-state $\leftarrow$ EVENT $]$ 
%\STATE become DONE
%
%\STATE $ $
%\STATE \textbf{DONE}
%
%\end{algorithmic}
%\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Patches}
\label{sec:patches}

Die Patches können in NetLogo nicht als \emph{breed} modelliert werden. Die Funktionsaufrufe aus dem Kontext eines Patches sind daher problematisch. Es können keine Kontrollstrukturen oder ordentliche Zustandsübergänge zentral erstellt werden. Es wird daher von impliziten Zuständen von Patches die Rede sein.

%Lifecyle
\subsection{Implizite Zustände}
\label{sec:patch_states}
% NONE, WALL, SPREADING, IDLE, DONE, EVENT, EVENT-DONE

% Kategorie: Grundriss
% NONE
% WALL

% Kategorie: Zellulärer Automat
% NONE
% NONE, SPREADING, IDLE, DONE

% Kategorie: Gefahrensituation
% NONE, EVENT
% NONE, EVENT, EVENT_DONE
% DONE, EVENT
% DONE, EVENT, EVENT_DONE

Mit der Initialisierung aller Patches nach dem Einbinden eines Grundrisses passiert die Zustandsfestlegung anhand der Farbe eines Patches. Für diesen Schritt kann generell zwischen zwei Zuständen unterschieden werden. \verb|NONE| wird als leerer Raum angenommen, in dem sich Signal mit geringer Dämpfung ausbreiten können, Personen sich bewegen können ebenso wie das Giftgas. Der leere Raum wird im Grundriss über die Farbe \verb|white| ausgedrückt.

Patches mit der Farbe \verb|black| oder alle anderen Farben werden als Wände und Materialien mit hoher Dämpfung interpretiert. Die Patches gehen in den Zustand \verb|WALL| über. Dieser Zustand ist statisch.

\begin{figure}[!ht]
\centering
\includegraphics[height=0.6\textwidth]{simulationsumgebung/patch.eps}
\caption{Zustandsdiagramm der Patches}
\label{fig:patch}
\end{figure}

Auf Patches im Zustand \verb|NONE| werden die Personen, die Notausgänge und die Gefahrenevents platziert. Außerdem werden nur diese Patches mit Signal-Informationen geflutet. Ist dies der Fall, so nehmen die Patches die Zustände \verb|SPREADING|, \verb|IDLE| und \verb|DONE| an.

Patches im Zustand \verb|SPREADING| sind erstmalig von einem Notausgang mit Signalinformationen versehen worden. Patches in diesem Zustand verteilen die Signalstärke bzw. die Dämpfung an ihre benachbarten Patches, bei jedem Schritt wird die Dämpfung inkrementiert. Die Patches direkt unter einem Notausgang sind dabei die Ausgangspunkte für das Fluten.

Sobald ein Patch die Signal-Informationen von allen Notausgängen lokal gespeichert hat, wechselt es in den Zustand \verb|IDLE|. Hier wird auf ein besseres Signal eines jeden Notausgangs gewartet. Dies ist der Fall bei anderen Lauf- bzw. Ausbreitungswegen der Signalen insbesondere bei Grundrissen mit vielen punktuellen Wandfragmenten der Fall. Wird ein besseres Signal festgestellt, wird es verständlicherweise an die benachbarten Patches gemeldet.

Haben alle Patches in der Nachbarschaft einen optimalen Signalwert, geht dieses Patch in den Zustand \verb|DONE| über. Allerdings wird dieser Idealzustand nicht für alle Patches erreicht, insbesondere bei einem niedrigen \verb|exit-signal-strength|-Parameter. Eine Überlappung von zwei bis drei Signalen von Notausgängen ist in fast allen Fällen ausreichend für eine intelligente Flucht. Ist der nächstgelegene Notausgang blockiert, wird der zweitbeste Notausgang von der Person zur Evakuierung genutzt. Mit der Fortbewegung erhält sie permanent neue Informationen zu nahe gelegene oder blockierte Notausgänge.

Nach Abschluss der Signal-Flutung befinden sich die Patches entweder im Zustand \verb|NONE|, sofern die Signalreichweite aller Notausgänge zu gering ist, oder in \verb|DONE| mit Signalinformationen.

Analog zum Fluten mit Signal-Informationen initiieren Gefahrenevents direkt unter sich ein Patch im Zustand \verb|EVENT|. Diese Gasfreisetzung bereitet sich genau wie die Signale aus, es wird jedoch nur der Zustand der Patches angepasst. Außerdem ist die Gasausbreitung an Nachbarn als einmalig initial und darauf folgend als kontinuierlich anzusehen. Patches, die die Event-Information an ihre Nachbarn weitergegeben haben, wechseln in den Zustand \verb|EVENT_DONE|. Die Patches werden programmatisch bei der weiteren Ausbreitung ausgeschlossen. Es ist eine Laufzeitreduzierung festzustellen.

Personen detektieren Patches im Zustand \verb|EVENT| und \verb|EVENT_DONE| als Gefahrensituation.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Ressourcen der Simulationsumgebung}
\label{sec:ressourcen}

Die Simulationsumgebung wird über die Datei \verb|Evakuierung.nlogo| gestartet. Der Programmcode ist nach Funktion und \emph{Breed}-Klasse unterteilt.

\paragraph{Gefahrensituationen} 

\begin{verbatim}
event.nls
\end{verbatim}

Die Quellcode-Datei \verb|event.nls| beinhaltet den Lebenszyklus der Gefahrenevents und deren Zustandsübergangsprotokoll. 

\paragraph{Lokalisierung}

\begin{verbatim}
locate.nls
\end{verbatim}

In dieser Datei wird der \emph{Multilateration Algorithmus} zur Lokalisierung aus dem Paper \cite{Jonathan.2004} implementiert.

\paragraph{Notausgänge}

\begin{verbatim}
exit.nls
exit-cellular-automaton.nls
\end{verbatim}

Die Quellcode-Datei \verb|event.nls| steuert den Setup und den Lebenszyklus der Notausgänge. Mittels \verb|exit-cellular-automaton.nls| wird der Orientierungsalgorithmus auf Basis des zellulären Automats realisiert.

\paragraph{Personen}

\begin{verbatim}
person.nls
person-gsn.nls
person-linking.nls
\end{verbatim}

\verb|person.nls| regelt den Setup der Personen und deren Lebenszyklus. \verb|person-gsn.nls| umfasst den Quellcode für die Kommunikation zwischen Personen und mit der Datei \verb|person-linking.nls| wird der Graph zwischen Personen erstellt.

\paragraph{Simulationswelt}

\begin{verbatim}
patch.nls
\end{verbatim}

Hier wird der Quellcode für den Lebenszyklus der \emph{Patches} definiert.